package leetcode每日一题.leetcode20212;


import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * 1. 问题描述
 *      给你一个整数数组nums和一个表示限制的整数limit,请你返回最长连续子数组的长度,
 *      该子数组中的任意两个元素之间的绝对差必须小于或者等于limit.如果不存在满足条件的子数组,则返回0.
 *
 * 2. 算法分析
 *      对于这个问题，本质上非常简单，如果当前子数组假设为[left,right],则如果这个区间满足两两元素的绝对差值
 *      小于等于limit，等价于当前数组的最大值和最小值的差值的绝对值小于等于limit，所以我们需要找出当前区间的
 *      最大最小值即可，这样我们可以使用单调队列来辅助维护当前区间的最大值和最小值
 *      思路1： 滑动窗口 + 单调队列
 *          设置两个队列queMax和queMin分别维护当前区间的最大值和最小值，其次设置左右窗口分别为left和right
 *          因为queMax和queMin是维护当前窗口中的最值，所以整个代码逻辑在于维护单调性。由于队列的特性是先进
 *          先出，队头进，队尾出，如果当前元素大于queMax队尾，此时需要将当前队尾元素出队，重复，直到当前队尾
 *          元素小于等于当前需要进队的元素，然后将当前元素入队，对于queMin而言也是类似，只不过是维护最小值
 *          这一部分是维护单调性，另外一部分就是何时更新满足条件的当前子数组的长度，如果当前队列都不空并且最
 *          大值队列的队尾和最小值队列的队尾的差值大于limit，此时需要出队，但是出队并不是直接出队，而是需要
 *          判断，如果当前left对应的元素恰好为queMin的最小值，出队，如果left对应的元素恰好为queMax的最大值
 *          出队，然后left右移动一位，这里也需要使用循环，直到满足条件，最后更新当前子数组的长度
 *
 *      这个题目本质上就是一道考察数据结构的问题，对于最值维护可以采用那些结构来维护，如果选对结构，此题的解决
 *      就不难了
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q023_绝对差不超过限制的最长连续子数组 {

    // 滑动窗口+单调队列
    public int longestSubarray1(int[] nums, int limit) {
        // 队列是先进先出，队头进，队尾出
        Deque<Integer> queueMax = new LinkedList<>(); // 维护当前最大值
        Deque<Integer> queueMin = new LinkedList<>(); // 维护当前最小值
        int n = nums.length;
        int left = 0;
        int right = 0;
        int res = 0;
        while(right < n) {
            // 如果当queueMax不为空其当前右窗口对应的元素大于队尾元素，此时需要出队，维护单调性
            while(!queueMax.isEmpty() && queueMax.peekLast() < nums[right]) {
                queueMax.pollLast();
            }
            // 如果当queueMin不为空其当前右窗口对应的元素小于队尾元素，此时需要出队，维护单调性
            while(!queueMin.isEmpty() && queueMin.peekLast() > nums[right]) {
                queueMin.pollLast();
            }
            // 当前元素入队
            queueMax.offerLast(nums[right]);
            queueMin.offerLast(nums[right]);
            // 此时我们需要判断当前窗口是否为满足条件的子数组
            // 所谓的满足条件，由于上述队列的含义，我们知道一个维护当前窗口的最大值，一个维护最小值
            // 所以两个队列的队尾元素的差值的绝对值就是这个子数组中的所有元素两两之间的最大差值，如
            // 果该差值小于等于limit，则当前区间的所有元素两两之间都满足小于等于limit
            while(!queueMin.isEmpty() && !queueMin.isEmpty() && queueMax.peekFirst() - queueMin.peekFirst() > limit) {
                if(nums[left] == queueMin.peekFirst()) {
                    queueMin.pollFirst();
                }
                if(nums[left] == queueMax.peekFirst()) {
                    queueMax.pollFirst();
                }
                left++;
            }
            res = Math.max(res,right - left + 1);
            right++;
        }
        return res;
    }

    // 滑动窗口+优先队列 代码逻辑于上述一致，只不过使用的是堆这种数据结构
    public int longestSubarray2(int[] nums, int limit) {
        PriorityQueue<Integer> heapMax = new PriorityQueue<>((n1,n2)->n2-n1); // 维护最大值
        PriorityQueue<Integer> heapMin = new PriorityQueue<>((n1,n2)->n1-n2); // 维护最小值
        int n = nums.length;
        int res = 0;
        int left = 0; int right = 0;
        while (right < n) {
            while (!heapMax.isEmpty() && heapMax.peek() < nums[right]) {
                heapMax.poll();
            }
            while (!heapMin.isEmpty() && heapMin.peek() > nums[right]) {
                heapMin.poll();
            }
            heapMax.add(nums[right]);
            heapMin.add(nums[right]);
            while (!heapMax.isEmpty() && !heapMin.isEmpty() && heapMax.peek() - heapMin.peek() > limit) {
                if (heapMax.peek() == nums[left]) {
                    heapMax.poll();
                }
                if (heapMin.peek() == nums[left]) {
                    heapMin.poll();
                }
                left++;
            }
            res = Math.max(res,right-left+1);
            right++;
        }
        return res;
    }

}
